package G.二叉搜索树;

import java.util.Stack;

public class _98_验证二叉搜索树 {

    /**
     * 自解：借助二叉搜索树中序遍历结果是递增数列这个性质
     * 中序遍历当前树 结果依次与栈顶的元素进行比对 如果大就push进去 如果小就直接返回false
     * ---修改：只需要获取上一个遍历的 所以不需要stack 只用一个变量即可
     * @param root
     * @return
     */

    int temp = Integer.MIN_VALUE;
    boolean isBsT = true;
    public boolean isValidBST(TreeNode root) {

        if (root == null){
            return true;
        }

// 写法有问题
//        if (isValidBST(root.left)){
//            if (root.val >temp){
//                temp = root.val;
//              //  return true;
//            }else {
//                isBsT = false;
//            }
//
//           isValidBST(root.right);
//
//        }else {
//            return false;
//        }
//        return true;

        //题解写法---把需要返回false的情况if出来 剩下的继续遍历 pre保留最后一次访问的
        if (root == null) {
            return true;
        }
        // 访问左子树
        if (!isValidBST(root.left)) {
            return false;
        }
        // 访问当前节点：如果当前节点小于等于中序遍历的前一个节点，说明不满足BST，返回 false；否则继续遍历。
        if (root.val <= temp) {
            return false;
        }
        temp = root.val;
        // 访问右子树
        return isValidBST(root.right);



    }

}
